//有效括号
class Solution {
public:
    bool isValid(string s) {
        vector<int> stack;
        for (auto& c : s) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push_back(c);
            } else {
                if (stack.empty())
                    return false;
                if ((c == ')' && stack.back() == '(') ||
                    (c == ']' && stack.back() == '[') ||
                    (c == '}' && stack.back() == '{'))
                    stack.pop_back();
                else
                return false;    
            }
        }
        if (stack.empty())
            return true;
        return false;
    }
};

//搜索旋转排序数组
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (target == nums[0])
            return 0;
        int l = 0, r = nums.size() - 1;
        int t = nums[0];
        while (l < r) {
            int mid = l + (r - l) / 2;

            if (nums[mid] >= t)
                l = mid + 1;
            else
                r = mid;
        }

        if (nums[r] >= t) {
            int left, right;
            left = 0, right = nums.size() - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (nums[right] != target)
                return -1;
            else
                return right;
        }
        //  cout << r;
        int left, right;
        if (target > nums[0]) {
            left = 0, right = r - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target)
                    right = mid;
                else
                    left = mid + 1;
            }
            if (right >= 0 && nums[right] != target)
                return -1;
        } else {
            left = r, right = nums.size() - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] >= target)
                    right = mid;
                else
                    left = mid + 1;
            }
            // cout << right;
            if (nums[right] != target)
                return -1;
        }
        return right;
    }
};